A. Field of the Invention
The present invention is directed to a system for determining exits and entrances for a region in a network.
B. Description of the Related Art
Computers have revolutionized the idea of modeling systems for enhanced study and use of the systems. One example is the modeling of a system as a network. A network is defined in its most general sense as something that includes a number of paths that interconnect or branch out. Many systems that involve decisions can be modeled as a network. For example, a manufacturing process or a system of providing medical treatment can be modeled as a network of decision points and actions between decision points. This network can be represented in electronic form and stored on a processor readable storage medium so that software can be created for using the network model to study or use the system.
One example of a useful network that can be stored in electronic form is the electronic map, which includes geographically referenced electronic data quantifying a physical, social or economic system. The range of information included in electronic maps is unlimited; for example, electronic maps could include distances between elements, travel time, lot numbers, tax information, tourist information, processing time, waiting time, etc. Additionally, storing a map as a file on a computer allows for unlimited software applications to manipulate that data. One advantage of the computer readable geographic map is that it provides for storing and determining costs associated with various nodes and links in the map. Examples of such costs include time, distance, tolls paid, ease of turning, quality of scenery, etc.
Electronic maps, as well as other networks, can be used for pathfinding, which is a method for computing a route between an origin and a destination. A computer readable map that is used for pathfinding must carry information about the connectivity of a road network, including information about the ways in which pieces of road do or do not connect to each other. For example, such information may include where there are ordinary intersections, where there are overpasses, where turns are restricted, and so on. This information may be combined with cost information, so that a route with a specified cost parameter may be determined.
The process of finding a path may require a great deal of computation. Several schemes have been developed for improving the speed of such computations. Some schemes reduce the number of elements that are considered in a pathfinding exploration. Other schemes provide for ways of clustering or packing the data to be processed in files, so that the processing may be expedited. However, the prior art attempts to reduce processing time have not been sufficient in light of the size of many large databases.
Thus, there is a need for a system that further reduces the computation time needed to perform a pathfinding process.